package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

/**
 * 树的子结构
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9826.%20%E6%A0%91%E7%9A%84%E5%AD%90%E7%BB%93%E6%9E%84/README
 */
public class P26 {
    public static void main(String[] args) {
        TreeNode nod1 = new TreeNode(1);
        TreeNode nod2 = new TreeNode(2);
        TreeNode nod4 = new TreeNode(4);
        nod4.left = nod1;
        nod4.right = nod2;
        TreeNode nod5 = new TreeNode(5);
        TreeNode nod3 = new TreeNode(3);
        nod3.left = nod4;
        nod3.right = nod5;

        TreeNode nod_4 = new TreeNode(4);
        nod_4.right = new TreeNode(2);

        Solution solution = new P26().new Solution();
        boolean subStructure = solution.isSubStructure(nod3, nod_4);
        System.out.println(subStructure);
    }




    /**
     * https://blog.csdn.net/weixin_44285445/article/details/108397803?spm=1001.2101.3001.6650.6&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-6-108397803-blog-114806133.pc_relevant_multi_platform_featuressortv2dupreplace&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-6-108397803-blog-114806133.pc_relevant_multi_platform_featuressortv2dupreplace&utm_relevant_index=10
     * 若树B是树A的子结构，则子结构的根节点可能是树A的任务一个节点。因此，判断树B是否是树A的子结构，需要完成一下两步：
     * 1.先序遍历树A的每个节点n(A)；对应函数（isSubStructure(A, B)）
     * 2.判断A中以n(A)为根节点的子树是否包含树B，对应函数（dfs(A, B)）
     */
    class Solution {


        /**
         * 1.特例处理：当树A为空或者树B为空时，直接返回false
         * 2.返回值：若树B是树A的子结构，则必须满足一下三种情况之一，因此用或||连接
         *      1.以节点A为根节点的子树包含树B，对应dfs(A, B)
         *      2.树B是树A左子树的子结构，对应isSubStructure(A.left, B)
         *      3.树B是树A右子树的子结构，对应isSubStructure(A.right, B)
         */
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if (A == null || B == null) {
                return false;
            }
            return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }

        /**
         * 1.终止条件
         *     1.当节点B为空时：说明树B已匹配完毕（越过叶子节点），因此返回true；
         *     2.当节点A为空时：说明已经越过树A叶子，即匹配失败，返回false；
         *     2.当节点A和B的值不同：说明匹配失败，返回false；
         * 2.返回值
         *
         *     1.判断A和B的左子树节点是否相等，即dfs(A.left, B.left)
         *     2.判断A和B的右子树节点是否相同，即dfs(A.right, B.right)
         *
         */
        private boolean dfs(TreeNode A, TreeNode B) {
            if (B == null) {
                return true;
            }
            if (A == null || A.value != B.value) {
                return false;
            }
            // 此时A.value == B.value，继续递归
            return dfs(A.left, B.left) && dfs(A.right, B.right);
        }
    }
}
